import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-27
 * Time:8:08
 */
class TreeNode{
    public int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
class Solution {
    List<List<Integer>> listList=new LinkedList<>();
    //Stack<TreeNode> stack= new Stack<>();
    Queue<TreeNode> queue=new LinkedList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return listList;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list=new LinkedList<>();
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur= queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            listList.add(list);
        }
        return listList;
    }
    //建立二叉树
    int cur=1;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //根节点
        TreeNode root= new TreeNode(preorder[0]);
        //找其中的位置
        int ret=find(inorder,0,inorder.length,preorder[0]);
        root.left=buildTreeChild(preorder,inorder,0,ret-1);
        root.right=buildTreeChild(preorder,inorder,ret+1,inorder.length-1);
        return root;
    }
    public int find(int[] inorder, int begin,int end,int val){
        for (int i = begin; i < end; i++) {
            if(inorder[i]==val){
                return val;
            }
        }
        return -1;
    }
        public TreeNode buildTreeChild(int[] preorder, int[] inorder,int begin,int end){
            //已经找完了
            if(begin>end){
                return null;
            }
            //开始找下一个
            int val=preorder[cur];
            TreeNode root= new TreeNode(preorder[cur]);
            cur++;
            if(begin==end){
                return root;
            }
            int ret=find(inorder,begin,end,val);
            //里面没有
            if(ret==-1){
                return null;
            }
            root.left=buildTreeChild(preorder,inorder,0,ret-1);
            root.right=buildTreeChild(preorder,inorder,ret+1,inorder.length-1);
            return root;
    }
}
public class Test {
    public static TreeNode create(){
        TreeNode list1=new TreeNode(1);
        TreeNode list2=new TreeNode(2);
        TreeNode list3=new TreeNode(3);
        TreeNode list4=new TreeNode(4);
        TreeNode list5=new TreeNode(5);
        list1.left=list2;
        list1.right=list3;
        list3.left=list4;
        list3.right=list5;
        return list1;
    }

    public static void main(String[] args) {
        TreeNode root=create();
        Solution solution=new Solution();
        List<List<Integer>> list=solution.levelOrder(root);
        System.out.println(list);
    }
}
